In order to speed up the retrieval time for data in computer systems, a cache memory is often used to provide ready access of the data to the computer, without the need to address and access a much slower main memory.
A CAM (content addressable memory) is a memory structure whose function is to indicate which of the internal data locations contains a data word presented to it as a `search key`. A data word is initially written in to the CAM at a location indicated by an address input and thereafter if the exact same address input appears on the `search key` input, an indication of a match, called a match flag, is asserted and the `Location Number` of the data location containing the search key data is also providd as an output.
The location number output of a CAM is often used as an address input to a RAM. The RAM then provides as an output the data residing at the location corresponding to the locaton number of the original match in the CAM.
A CAM/RAM combination may conveniently be used to implement a cache: The search key provided is the address (logical or physical) where a required data word resides in main memory. If the address is present in the CAM, then a match is found and the RAM, reading fromthe location provided by the CAM location number, supplies the data which resides at that address in main memory. This circumvents the lengthy address translation and memory access procedures. If on the other hand the address is not found in the cache, then the normal read from main memory procedures is followed. When the data returns, it is stored along with its address in the CAM and RAM. Any time this address is subsequently read, a match will be found and the data will be provided.
The overriding problem with using a cache is that the data in main memory may be changed from time to time. If a memory location whose address is stored in the CAM has its contents changed, then the data stored in the RAM is no longer correct. At this time either the correct data may be written into the RAM or the address must be removed from the CAM. The process of updating the cache to reflect the main memory contents is referred to as maintaining coherency of the cache.
The CHAMP processor, discussed herein in connection with FIGS. 4A and 4B, is a stack based architecture. The most frequently used data words are items from an `expression stack` which is used continuously as processing is done. Items in the stack are identified by a logical addressing scheme known as `address couples` which give the position of the word in the stack relative to the base of the stack. These address couples occur frequently in the code stream with a relatively small number of them being used very repetitively at any given time. These address couples can be translated into "absolute" addresses by the processor but the process is tedious and involves execution of many processor steps and often may require several memory accesses. The performance of a processor can be increased many times over by using a cache which provides the required data without delay.
The ACAM cache (Address Couple Associative Memory) described hereinafter is such a caching scheme. It allows execution of instructions in the processor without any delay in waiting for data when a cache hit occurs. The achievable hit rate is high and coherency is continuously maintained.
A cache system such as shown in FIG. 1B, provides for an association between a content addressable memory (CAM) 14 and a RAM 18.sub.m which has a word of data associated with each location of the content addressable memory. The content addressable memory carries address couples in a list and each address is connected to a location in the associated RAM memory which holds the data corresponding to that address, while the associated RAM location holds the data residing at the corresponding physical address in main memory. Thus both address translation and data access is provided.
When the processing unit sends an address couple to the content addressable memory 14, if there is a match or a "hit", then the data which correspondingly resides in the associated location of the RAM memory 18.sub.m will be immediately provided to the processing unit (10).